/*
 * ds.h
 *
 *  Created on: Sep 14, 2012
 *      Author: xx255000
 */

#ifndef DS_H_
#define DS_H_

#include <queue>
#include <stack>

#include "base.h"

typedef struct LinkListNode {
	int value;
	LinkListNode* next;
} LinkListNode;

LinkListNode* CreateLinkedList(int* a, int from, int to, LinkListNode* l);

void DestroyLinkedList(LinkListNode* l);

void PrintLinkedList(LinkListNode* l);

LinkListNode* ReverseLinkedList(LinkListNode* l);

LinkListNode* ReverseLinkedListRecursively(LinkListNode* l);

bool TwoLinkedListCrosses(LinkListNode* h, LinkListNode* l);

void PrintBackwardsKthNode(LinkListNode* l, int k);



typedef struct TreeNode {
	int value;
	TreeNode* left;
	TreeNode* right;
} TreeNode;

typedef struct TreeNode DBListNode;

TreeNode* CreateTree(int *a, int from, int to, TreeNode* r);

void DestroyTree(TreeNode* n);

void RecursivelyPreVisitTree(TreeNode* n);

void RecursivelyMidVisitTree(TreeNode* n);

void RecursivelyPostVisitTree(TreeNode* n);

TreeNode* RecursivelySwitchTree(TreeNode* n);

void SwitchTree(TreeNode* n);

void VisitTreeByLevel(TreeNode* n);

bool ExistPathEqualsN(TreeNode* t, int n);

void PrintPathEqualsN(TreeNode* t, int n);

TreeNode* GetNearestCommonParent(TreeNode* n, TreeNode* n1, TreeNode* n2);

int GetMaxSubTreeSum(TreeNode* n);

void ConvertToDBList(TreeNode* t, DBListNode* &l);

void PrintDBList(DBListNode* l);

void DeleteDBList(DBListNode* l);

void PrintStack(stack<int> &s);

stack<int> & RecursivelyReverseStack(stack<int> &s);

#endif /* DS_H_ */
